package com.copa.l53;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author copa
 * @createDate 2022-05-10 17:26
 * @function 分治法 这时候我是第一次听说
 */
public class Test2 {
    public int maxSubArray(int[] nums) {
        return getMax(nums, 0, nums.length - 1);
    }

    private int getMax(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        int leftMax = getMax(nums, left, mid);
        int rightMax = getMax(nums, mid + 1, right);
        int midMax = getCrossMax(nums, left, right);
        Integer max = Arrays.asList(leftMax, rightMax, midMax).stream().max(Integer::compare).get();
        return max;
    }

    private int getCrossMax(int[] nums, int left, int right) {
        int mid = left + (right - left) / 2;
        int leftSum = nums[mid];
        int temp = nums[mid];
        for (int i = mid - 1; i >= left; i--) {
            temp += nums[i];
            leftSum = Math.max(temp, leftSum);
        }
        int rightSum = nums[mid + 1];
        temp = nums[mid + 1];
        for (int i = mid + 2; i <= right; i++) {
            temp += nums[i];
            rightSum = Math.max(temp, rightSum);
        }
        return leftSum + rightSum;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5, 4, -1, 7, 8};
        //int[] nums = new int[]{-1, -2};
        System.out.println(new Test2().maxSubArray(nums));
    }
}
